<?php
    class Solution {

        /**
         * 67. 二进制求和
         *
         * @param String $a
         * @param String $b
         * @return String
         */
        function addBinary67($a, $b) {
            $jian = strlen($a) - strlen($b);
            if($jian >= 0 ){
                $sum = $a;
                $few = $b;
                $count = strlen($b);
            }else{
                $sum = $b;
                $few = $a;
                $count = strlen($a);
            }
            $jian = abs($jian);
            $check = '0';
            for($i = $count-1; $i >= 0; $i--) {
                if($sum[$jian+$i] == $few[$i]){
                    $sum[$jian+$i] = $check;
                    if($few[$i] == '1'){
                        $check = '1';
                    }else{
                        $check = '0';
                    }
                    continue;
                }
                if($check == '1'){
                    $sum[$jian+$i] = '0';
                }else{
                    $sum[$jian+$i] = '1';
                    $check = '0';
                }
            }
            if($check == '1'){
                for($i = strlen($sum)-$count-1 ; $i >= 0; $i--){
                    if($sum[$i] == '1'){
                        $sum[$i] = '0';
                        continue;
                    }
                    $sum[$i] = $check;
                    break;
                }
                if(strlen($a) == strlen($b)){
                    $sum = '1'.$sum;
                }
            }
            if($sum[0] == 0 && (!$sum[1] || $check == 1)){
                if(strlen($sum) != 1 || $a[0] == 1)
                    $sum = '1' . $sum;
            }
            return $sum;
        }

        /**
         * 69. x 的平方根
         * @param Integer $x
         * @return Integer
         */
        function mySqrt69($x) {
            $count = 1;
            while($count*$count <= $x) {
                $count++;
            }
            return $count-1;
        }

        /**
         * 70. 爬楼梯
         * @param Integer $n
         * @return Integer
         */
        function climbStairs70($n) {

        }

        /**
         * @param ListNode $head
         * @return ListNode
         */
        function deleteDuplicates83($head) {

        }

        /**
         * 88. 合并两个有序数组
         * @param Integer[] $nums1
         * @param Integer $m
         * @param Integer[] $nums2
         * @param Integer $n
         * @return NULL
         */
        function merge88(&$nums1, $m, $nums2, $n) {
            $new = [];
            $left = 0;
            $right = 0;
            for($i = 0; $i < $m+$n; $i++) {
                if(!$nums1[$left] && $left >= $m){
                    $new[] = $nums2[$right];
                    $right++;
                    continue;
                }
                if(!$nums2[$right] && $right >= $n){
                    $new[] = $nums1[$left];
                    $left++;
                    continue;
                }
                if($nums1[$left] <= $nums2[$right]){
                    $new[] = $nums1[$left];
                    $left++;
                }else{
                    $new[] = $nums2[$right];
                    $right++;
                }
            }
            foreach($new as $k=>$n) {
                $nums1[$k] = $n;
            }
            return $nums1;
        }

        /**
         * @param TreeNode $root
         * @return Integer[]
         */
        function inorderTraversal94($root) {

        }



    }

    $solution = new Solution();
    $nums1 = [1,2,3,0,0,0];
    $nums2 = [2,5,6];
    $m = 3;
    $n = 3;
//    $solution->merge88($nums1, $m, $nums2, $n);
    var_dump($solution->merge88($nums1, $m, $nums2, $n));


?>